/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* selfDividingNumbers(int left, int right, int* returnSize) {
    int* nums = (int*)malloc(sizeof(int) * (right - left + 1));
    *returnSize = 0;

    for (int i = left; i <= right; i++)
    {
        int temp = i;
        int flag = 1;
        while (temp)
        {
            int num = temp % 10;
            if (num == 0 || i % num != 0)
            {
                flag = 0;
                break;
            }
            temp /= 10;
        }
        if (flag == 1)
        {
            nums[(*returnSize)++] = i;
        }
    }

    return nums;
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 // int* productExceptSelf(int* nums, int numsSize, int* returnSize){
 //     int *ret = (int *)malloc(sizeof(int) * numsSize);
 //     *returnSize = numsSize;

 //     int *left = (int *)malloc(sizeof(int) * numsSize);
 //     int *right = (int *)malloc(sizeof(int) * numsSize);

 //     left[0] = 1;
 //     right[numsSize - 1] = 1;
 //     for(int i = 1; i < numsSize; i++)
 //         left[i] = left[i - 1] * nums[i - 1];
 //     for(int i = numsSize - 2; i >= 0; i--)
 //         right[i] = right[i + 1] * nums[i + 1];

 //     for(int i = 0; i < numsSize; i++)
 //         ret[i] = left[i] * right[i];

 //     return ret;
 // }

 // int* productExceptSelf(int* nums, int numsSize, int* returnSize){
 //      int *ret = (int *)malloc(sizeof(int) * numsSize);
 //      *returnSize = numsSize;

 //     ret[0] = 1;
 //     for(int i = 1; i < numsSize; i++)
 //         ret[i] = ret[i - 1] * nums[i - 1];

 //     int sub = 1;
 //     for(int i = numsSize - 1; i >= 0; i--)
 //     {
 //         ret[i] = ret[i] * sub;
 //         sub *= nums[i];
 //     }

 //     return ret;
 // }
 // int* productExceptSelf(int* nums, int numsSize, int* returnSize){
 //     int *ret = (int *)malloc(sizeof(int) * numsSize);
 //     *returnSize = numsSize;

 //     for(int i = 0; i < numsSize; i++)
 //         ret[i] = 1;

 //     int leftSub = 1;
 //     int rightSub = 1;
 //     for(int i = 0, j = numsSize - 1; i < numsSize; i++,j--)
 //     {
 //         ret[i] *= leftSub;
 //         ret[j] *= rightSub;

 //         leftSub *= nums[i];
 //         rightSub *= nums[j];
 //     }

 //     return ret;
 // }
 // int* productExceptSelf(int* nums, int numsSize, int* returnSize){
 //     int *ret = (int *)malloc(sizeof(int) * numsSize);
 //     *returnSize = numsSize;

 //     int sub = 1;
 //     for(int i = 0; i < numsSize; i++)
 //         sub *= nums[i];

 //     for(int i = 0; i < numsSize; i++)
 //         ret[i] = sub / nums[i];

 //     return ret;
 // }
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int* ret = (int*)malloc(sizeof(int) * numsSize);
    *returnSize = numsSize;

    int leftSub = 1;
    for (int i = 0; i < numsSize; i++)
    {
        ret[i] = leftSub;
        leftSub *= nums[i];
    }

    int rightSub = 1;
    for (int i = numsSize - 1; i >= 0; i--)
    {
        ret[i] *= rightSub;
        rightSub *= nums[i];
    }

    return ret;
}